/*
 * @Author: 缄默
 * @Date: 2021-11-10 20:16:06
 * @LastEditors: 缄默
 * @LastEditTime: 2021-11-11 20:41:30
 */

//判断t1树是否包含t2树全部的拓扑结构

#include <iostream>
#include <vector>
#include <stack>
#include "../../DataStructure/tree.hpp"

using namespace std;

bool contains(TreeNode* t1, TreeNode* t2);
bool check(TreeNode* t1, TreeNode *t2);
int main() {
    vector<int> preOrder({4, 2, 1, 0, 3, 6, 5, 7});
    vector<int> inOrder({0, 1, 2, 3, 4, 5, 6, 7});
    TreeNode* head = buildTree(preOrder, inOrder, 0, 0, preOrder.size() - 1);
    vector<int> preOrder1({2, 1, 3});
    vector<int> inOrder1({1, 2, 3});
    TreeNode* head1 = buildTree(preOrder1, inOrder1, 0, 0, preOrder1.size() - 1);
    cout << contains(head, head1) << endl;
    return 0;
}

// 判断t1是否有子树t2
bool contains(TreeNode* t1, TreeNode* t2) {
    if (t1 == nullptr) return false;
    return check(t1, t2) || contains(t1->left, t2) || contains(t1->right, t2);
}
//判断以t1为头节点的树是否是t2
bool check(TreeNode* t1, TreeNode *t2) {
    if (t2 == nullptr && t1 == nullptr) return true;
    else if (t2 != nullptr && t1 != nullptr) return t1->val == t2->val && check(t1->left, t2->left) && check(t1->right, t2->right);
    return false;
}